package com.tree.leetcode.dubblePointer;

import java.util.Arrays;

/**
 * @ClassName com.tree.leetcode.dubblePointer
 * Description: 283. 移动零
 * <p>
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 * <p>
 * 输入: nums = [0]
 * 输出: [0]
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 104
 * -231 <= nums[i] <= 231 - 1
 * <p>
 * <p>
 * 进阶：你能尽量减少完成的操作次数吗？
 * </p>
 * @Author tree
 * @Date 12/10/23 4:55 PM
 * @Version 1.0
 */
public class MoveZeroes_283 {

    public static void main(String[] args) {
//        int[] nums = new int[]{0, 1, 0, 3, 12,0 ,1};
        int[] nums = new int[]{0,1};
//        moveZeroes(nums);
        moveZeroes2(nums);


    }

    /**
     * 方法一：双指针法
     * i --> 代表每次移动向前指针
     * j --> 代表最后一个可以交换的位置
     * @param nums
     */
    public static void moveZeroes(int[] nums) {

        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if (nums[i] != 0){
                swap(i,j,nums);
//                nums[j] = nums[i];
//                nums[i] = 0;
                System.out.println("第" + i + "次交换:" + Arrays.toString(nums)+ "指针i的位置：" + i + "; 指针B的位置：" + j);
                j++;
            }

            //当前元素!=0，就把其交换到左边，等于0的交换到右边
//            if(nums[i]!=0) {
//                int tmp = nums[i];
//                nums[i] = nums[j];
//                nums[j++] = tmp;
//            }

        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 方法二：2次for循环
     * 第一次， 记录有0的次数， 并且出现0的位置的值
     * 第二次， 0的次数替换最后的
     * @param nums
     */
    public static void moveZeroes2(int[] nums) {
        System.out.println("原始串："+Arrays.toString(nums));

        int zeroLen = 0;
        //j --> 代表最后一个可以交换的位置
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                zeroLen++;
            }else {
               nums[j] = nums[i];
               j++;
            }
        }
        System.out.println("zeroLen="+zeroLen+";nums="+Arrays.toString(nums));
        for (int i = nums.length -1; zeroLen>0  ;zeroLen--,i--) {

            System.out.println("zeroLen="+zeroLen+"; i = "+i);
            nums[i] = 0;
        }
        System.out.println(Arrays.toString(nums));



    }

    /**
     * 交换2个数
     * @param i
     * @param j
     * @param nums
     */
    private static void swap(int i, int j, int[] nums) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
}
